%\begin{abstract}
%We consider the \emph{online} version of the well known Principal Component Analysis (PCA) problem. In standard PCA, the input to the problem is a set of vectors 
%$\matX_1,\ldots x_n$ in $\R^d$ and a target dimension $k < d$; the output
%is a set of vectors $y_1,\ldots, y_n$ in $\R^k$ that minimizes the quantity:
%$$ \min_{\Phi \in \iso_{d,k}} \sum_{t=1}^{n} \|x_i - \Phi y_i\|_2^2,$$ 
%where 
%$$\iso_{d,k} =  \{  \Phi \in \R^{d \times k} | \forall y \in \R^k \;\; \|\Phi y\|_2 = \|y\|_2\}.$$
%
%In the online setting, the vectors $\matX_t$ are presented to the algorithm one by one, and for every presented $\matX_t$ the algorithm \emph{must} output a vector $y_t$ before receiving $\matX_{t+1}$. 
%This paper presents a deterministic approximation algorithm for the above setting of online PCA. 
%To our best knowledge, our work is the \emph{first} addressing online Principal Component Analysis from the above \emph{standard} perspective. 
%\end{abstract}


\begin{abstract}
We consider the \emph{online} version of the well known Principal Component Analysis (PCA) problem. In standard PCA, the input to the problem is a set of vectors 
$\x_1,\ldots \x_n$ in $\R^d$ and a target dimension $k < d$; the output
is a set of vectors $\y_1,\ldots, \y_n$ in $\R^k$ that minimizes the quantity:
$ \min_{\matPhi} \sum_{t=1}^{n} \|\x_t - \matPhi \y_t\|_2^2,$ where $\matPhi \in \R^{k \times d}$ is restricted to be an ``isometry''. 
In the online setting, the vectors $\x_t$ are presented to the algorithm one by one, and
for every presented $\x_t$ the algorithm \emph{must} output a vector $\y_t$ before receiving $\x_{t+1}$. The quality of the result, however, is measured in exactly the same way. 
%This is a natural cost function for online PCA and one that is especially useful for streaming data mining and machine learning.
This paper presents the \emph{first} approximation algorithms for this setting of online PCA. 
Our algorithms produce $\y_t \in \R^\ell$ with $\ell = O(k\cdot \operatorname{poly}(1/\eps))$ such that 
$$ \min_{\matPhi} \| \matX - \matPhi \matY\|_{\mathrm{F}}^2 \le \OPT_k + \varepsilon \cdot
\FNormS{\matX}.$$
Here, $\matX = [\x_1,\dots,\x_n]$,  $\matY = [\y_1,\dots,\y_n]$, and 
$\OPT_k$ is the cost from the optimal offline solution for PCA with inputs 
$\matX$ and $k$. 
\end{abstract}
